﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//剑指 Offer II 039. 直方图最大矩形面积❤️
class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		int n = heights.size();
		vector<int>left(n);
		vector<int>right(n);
		stack<int>st;
		for (int i = 0; i < n; i++)
		{
			//单调栈
			//找到左边第一个比我小的，没有赋值为-1
			while (!st.empty() && heights[st.top()] >= heights[i])
			{
				st.pop();
			}
			left[i] = st.empty() ? -1 : st.top();
			st.push(i);
		}
		st = stack<int>();
		for (int i = n - 1; i >= 0; i--)
		{
			//找到右边第一个比我小的下标，没有赋值为n
			while (!st.empty() && heights[st.top()] >= heights[i])
			{
				st.pop();
			}
			right[i] = st.empty() ? n : st.top();
			st.push(i);
		}
		int res = 0;
		for (int i = 0; i < n; i++)
		{
			res = max(res, (right[i] - left[i] - 1) * heights[i]);
		}
		return res;
	}
};